package com.test.daily.leetcode.y2021.m11.day1109;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2021/11/9 上午 11:57
 * @version: 1.0
 */
public class Code02_FindMinStep {

    private char[] colors = {'R', 'Y', 'B', 'G', 'W'};
    private int[] map = new int[26];
    private int ans;

    public int findMinStep(String board, String hand) {
        ans = Integer.MAX_VALUE;
        for (int i = 0; i < hand.length(); i++) {
            map[hand.charAt(i) - 'A']++;
        }
        dfs(new StringBuilder(board), 0);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

    public void dfs(StringBuilder board, int step) {
        if (step >= board.length()) {
            return;
        }
        if (board.length() == 0) {
            ans = Math.min(ans, step);
            return;
        }
        for (int i = 0; i < board.length(); i++) {
            int j = i;
            char c = board.charAt(i);
            while (j + 1 < board.length() && board.charAt(j + 1) == c) {
                j++;
            }
            if (j - i == 0 && map[board.charAt(i) - 'A'] >= 2) {
                StringBuilder tmp = new StringBuilder(board);
                tmp.insert(i, c + "" + c);
                map[c - 'A'] -= 2;
                dfs(elimate(tmp), step + 1);
                map[c - 'A'] += 2;
            } else if (j - i == 1 ) {
                if(map[board.charAt(i) - 'A'] >= 1){
                    StringBuilder tmp = new StringBuilder(board);
                    map[c - 'A'] -= 1;
                    tmp.insert(i, c);
                    dfs(tmp, step + 2);
                    map[c - 'A'] += 1;
                }

                for (char color : colors) {
                    StringBuilder tmp = new StringBuilder(board);
                    if (color == c) {
                        continue;
                    }
                    tmp.insert(i + 1, color);
                    map[c - color] -= 1;
                    dfs(elimate(tmp), step+1);
                    map[c - color] += 1;
                }
            }
        }
    }

    public StringBuilder elimate(StringBuilder tmp) {
        boolean flag = true;
        while (flag) {
            flag = false;
            for (int i = 0; i < tmp.length(); i++) {
                int j = i + 1;
                while (tmp.charAt(j) == tmp.charAt(i) && j < tmp.length()) {
                    j++;
                }
                if (j - i >= 3) {
                    tmp.delete(i, j);
                    flag = true;
                }
            }
        }
        return tmp;
    }

}
